#include "DBFileIndex.h"
#include "util.h"
#include "assert.h"
using namespace std;

char tmpCharArray[2 * DB_DISK_PAGE_SIZE];

inline int RecordCmp(const char* key1, int key1Len, const char* key2, int key2Len)
{
	int dataLength = Min(key1Len, key2Len);
	int cmpResult = memcmp(key1, key2, dataLength);
	if(cmpResult == 0)
	{
		if(key1Len > key2Len)
			return 1;
		else if(key1Len < key2Len)
			return -1;
		else
			return 0;
	}
	else
		return cmpResult;
}

/**
* Funtion Description :binary search in a short array
* @para short* sArray
* short array
* @para int begin
* begin index
* @para int end
* end index
* @para int key
* search value
* @return int
* index of the result
* for example, the sArray is 1, 4, 7, 19
* for number 1, result = 0;
* for number 6, result = 1;
* by Author: Jimmy
*/
int BinSearch(short* sArray, int begin, int end, int key)
{
	while(begin <= end)
	{
		int mid = (begin+end)/2;
		if((key < sArray[mid]) || (sArray[mid] == -1))
			end = mid - 1;
		else if(key > sArray[mid])
			begin = mid + 1;
		else
			return mid;
	}
	return end;
}

/**
* Funtion Description : Search an record in a index page
* @para DBIndexPage* indexPage
* index page
* @para int pid
* the pid of the record
* @para int& indexResult
* index of this record in page(Return value)
* @return bool
* true: find key
* false: did not find key
* by Author: Jimmy
*/
bool SearchPage(DBIndexPage* indexPage, int pid, int& indexResult)
{
	if(indexPage->firstPageId == pid)
	{
		indexResult = -1;
		return true;
	}

	for(int i=0; i<DBINDEX_MAX_SLOT-1; i++)
	{
		if(indexPage->slot[i+1] == -1)
			break;
		RowID* rowid = (RowID*)(indexPage->data + indexPage->slot[i]);
		if(rowid->pageid == pid)
		{
			indexResult = i;
			return true;
		}
	}

	return false;
}

/**
* Funtion Description : Search an record in a index page
* @para DBLeafIndexPage* leafPage
* index page
* @para char* key
* key word to be searched
* @para int keyLength
* key length
* @para int& indexResult
* index of this keyword in page(Return value)
* -1 stands for (-1, 0),
* 3 stands for (3, 4), etc.
* @return bool
* true: find key
* false: did not find key
* by Author: Jimmy
*/
bool SearchPage(DBIndexPage* indexPage, const char* key
				   , int keyLength, int& indexResult)
{
	assert((indexPage->slot[0] > -2) 
		&& (indexPage->slot[0] < INDEX_DATA_SIZE));

	char* dataHead;
	short dataLength;
	int cmpResult;

	int begin = 0;
	int end = DBINDEX_MAX_SLOT - 2;
	while(begin <= end)
	{
		int mid = (end + begin)/2;
		if(indexPage->slot[mid+1] == -1)
		{
			end = mid - 1;
			continue;
		}
		dataHead = indexPage->data + indexPage->slot[mid] + sizeof(RowID);
		dataLength =indexPage->slot[mid+1] 
			- indexPage->slot[mid] - sizeof(RowID);
		cmpResult = RecordCmp(key, keyLength, dataHead, dataLength);
		if(cmpResult == 0)
		{
			indexResult = mid;
			return true;
		}else if(cmpResult > 0)
			begin = mid + 1;
		else
			end = mid - 1;
	}
	indexResult = end;
	return false;
}

void InitPageSlot(DBIndexPage* indexPage)
{
	for(int i=0; i<DBINDEX_MAX_SLOT; i++)
		indexPage->slot[i] = -1;
	indexPage->slot[0] = 0;
}

/**
* Funtion Description : Recursively Drop a page
* @para DBBufPage* bufPage
* The page we drop
* by Author: Jimmy
*/
void DBFileIndex::DropPage(DBBufPage* bufPage)
{
	DBIndexPage* indexPage = (DBIndexPage*)&(bufPage->page);
	if(indexPage->pageType == INDEX_TYPE_NONLEAF)
	{
		for(int i=0; i<DBINDEX_MAX_SLOT; i++)
		{
			if(indexPage->slot[i+1] == -1)
				break;
			else
			{
				int pid = ((RowID*)&(indexPage->data[indexPage->slot[i]]))->pageid;
				DBBufPage* leafBufPage = manager->DBFileOpenPage(pid);
				DropPage(leafBufPage);
			}
		}
	}

	manager->DBFileDeletePage(bufPage->pid);
}

void DBFileIndex::InsertToIndexPage(const char* key, int keyLength
								, DBBufPage* insertBufPage, RowID rowId)
{
	int indexResult;
	DBIndexPage* insertIndexPage = (DBIndexPage*)&(insertBufPage->page);
	char* origData;
	bool splitIf = (INDEX_DATA_SIZE - insertIndexPage->addHead 
		> keyLength + sizeof(RowID))
		&& (insertIndexPage->slot[DBINDEX_MAX_SLOT-2] == -1);
	// The last slot is reserved
	if(splitIf)
		origData = insertIndexPage->data;
	else
	{
		origData = tmpCharArray;
		memcpy_s(origData, insertIndexPage->addHead
			, insertIndexPage->data, insertIndexPage->addHead);
	}

	// insert data
	SearchPage(insertIndexPage, key, keyLength, indexResult);
	// fill data field
	int tailLength = insertIndexPage->addHead - insertIndexPage->slot[indexResult+1];
	int totalRecordLength = keyLength + sizeof(RowID);
	char* orighead = origData + insertIndexPage->slot[indexResult+1];
	memmove_s(orighead+totalRecordLength, tailLength, orighead, tailLength);
	memcpy_s(orighead+sizeof(RowID), keyLength, key, keyLength);
	*(RowID*)orighead = rowId;

	// change slot
	int tmpSlotdata = 0;
	int tmpSlotIndexResult = insertIndexPage->slot[indexResult+1];
	for(int i=indexResult+1; i<DBINDEX_MAX_SLOT; i++)
	{
		if(insertIndexPage->slot[i] == -1)
		{
			insertIndexPage->slot[i] = tmpSlotdata + totalRecordLength;
			break;
		}
		else
		{
			int tmp = insertIndexPage->slot[i];
			insertIndexPage->slot[i] = tmpSlotdata + totalRecordLength;
			tmpSlotdata = tmp;
		}
	}
	insertIndexPage->slot[indexResult+1] = tmpSlotIndexResult;
	insertIndexPage->addHead += totalRecordLength;

	if(splitIf)
	{
		// no need to split
		// debug
		return;
	}
	else
	{
		// too much data, split
		// alloc new page
		DBBufPage* newBufPage;
		int pid;
		manager->DBFileAllocPage(pid, newBufPage);
		DBIndexPage* newIndexPage = (DBIndexPage*)&(newBufPage->page);
		InitPageSlot(newIndexPage);
		newIndexPage->pageType = insertIndexPage->pageType;
		newIndexPage->parent = insertIndexPage->parent;
		newIndexPage->firstPageId = -1;

		int slotIndex = BinSearch(insertIndexPage->slot, 0
			, DBINDEX_MAX_SLOT-1, insertIndexPage->addHead/2)+1;

		// copy slot & data to new Page
		short moveHead = insertIndexPage->slot[slotIndex];
		short copyDataLen = insertIndexPage->addHead - moveHead;
		memcpy_s(newIndexPage->data, copyDataLen
			, origData+moveHead, copyDataLen);
		for(int i=slotIndex; i<DBINDEX_MAX_SLOT; i++)
		{
			if(insertIndexPage->slot[i] != -1)
			{
				newIndexPage->slot[i-slotIndex]
					= insertIndexPage->slot[i] - moveHead;
				insertIndexPage->slot[i] = -1;
			}
		}
		insertIndexPage->slot[slotIndex] = moveHead;
		newIndexPage->addHead = copyDataLen;
		insertIndexPage->addHead = moveHead;

		// copy slot & data to inserted Page
		copyDataLen = moveHead;
		memcpy_s(insertIndexPage->data, moveHead, origData, moveHead);

		// change the children's parent
		if(newIndexPage->pageType == INDEX_TYPE_NONLEAF)
		{
			for(int i=0; i<DBINDEX_MAX_SLOT; i++)
			{
				if(newIndexPage->slot[i+1] != -1)
				{
					int pid  = ((RowID*)&(newIndexPage->data[newIndexPage->slot[i]]))->pageid;
					DBBufPage* childBufPage = manager->DBFileOpenPage(pid);
					DBIndexPage* childIndexPage = (DBIndexPage*)&(childBufPage->page);
					childIndexPage->parent = newBufPage->pid;
				}
				else
					break;
			}
		}

		RowID newRowId;
		newRowId.pageid = newBufPage->pid;
		DBBufPage* parentBufPage = manager->DBFileOpenPage(newIndexPage->parent);
		if(newIndexPage->parent != -1)
			InsertToIndexPage(newIndexPage->data+sizeof(RowID)
			, newIndexPage->slot[1] - sizeof(RowID)
			, parentBufPage, newRowId);
		else
		{
			// root page split
			int pid;
			DBBufPage* rootBufPage;
			manager->DBFileAllocPage(pid, rootBufPage);
			DBIndexPage* rootIndexPage = (DBIndexPage*)&(rootBufPage->page);
			InitPageSlot(rootIndexPage);
			rootIndexPage->pageType = INDEX_TYPE_NONLEAF;
			rootIndexPage->parent = -1;
			rootIndexPage->firstPageId = insertBufPage->pid;
			
			// insert first data
			short insertKeyLength = newIndexPage->slot[1] - sizeof(RowID);
			memcpy_s(rootIndexPage->data + sizeof(RowID), insertKeyLength
				, newIndexPage->data + sizeof(RowID), insertKeyLength);
			((RowID*)rootIndexPage->data)->pageid = newBufPage->pid;
			rootIndexPage->slot[0] = 0;
			rootIndexPage->slot[1] = insertKeyLength + sizeof(RowID);
			rootIndexPage->addHead = insertKeyLength + sizeof(RowID);

			// set child page
			insertIndexPage->parent = newIndexPage->parent
				= rootBufPage->pid;

			// update rootid
			rootId = rootBufPage->pid;
		}
	}
}

void DBFileIndex::DeleteFromIndexPage(int keyIndex, DBBufPage* delBufPage)
{
	// delete this record
	DBIndexPage* delIndexPage = (DBIndexPage*)&(delBufPage->page);
	
	// special treatment for first record
	int delIndex;
	if(keyIndex == -1)
	{
		delIndex = 0;
		if(delIndexPage->addHead != 0)
			delIndexPage->firstPageId = ((RowID*)(delIndexPage->data))->pageid;
		else
		{
			delIndexPage->firstPageId = -1;
			goto FurthurDel;
		}
	}
	else
		delIndex = keyIndex;

	// del data & slot
	int moveHead = delIndexPage->slot[delIndex+1];
	int delRecordTotalLength = delIndexPage->slot[delIndex+1]
		- delIndexPage->slot[delIndex];
	int moveLength = delIndexPage->addHead - moveHead;
	memmove_s(delIndexPage->data + moveHead - delRecordTotalLength
		, moveLength, delIndexPage->data + moveHead, moveLength);
	for(int i=delIndex; i<DBINDEX_MAX_SLOT-1; i++)
	{
		if(delIndexPage->slot[i+1] == -1)
		{
			delIndexPage->slot[i] = -1;
			break;
		}
		delIndexPage->slot[i] = delIndexPage->slot[i+1]
			- delRecordTotalLength;
	}
	delIndexPage->slot[DBINDEX_MAX_SLOT - 1] = -1;
	
	delIndexPage->addHead -= delRecordTotalLength;

FurthurDel:
	// Furthur del(no children)
	if((delIndexPage->addHead == 0) && (delIndexPage->firstPageId == -1))
	{
		// not root page
		if(delIndexPage->parent != -1)
		{
			DBBufPage* parentBufPage = manager->DBFileOpenPage(
				delIndexPage->parent);
			DBIndexPage* parentIndexPage 
				= (DBIndexPage*)&(parentBufPage->page);

			// del from parent
			int indexResult;
			if(!SearchPage(parentIndexPage, delBufPage->pid, indexResult));
				assert(false);	// impossible!
			DeleteFromIndexPage(indexResult, parentBufPage);

			// del myself
			manager->DBFileDeletePage(delBufPage->pid);
		}
	}
}

/**
* Funtion Description : Find out the leaf page contain key
* @para int rootId
* root pid
* @para char* key
* key
* @para int keyLength
* key length
* @return DBBufPage*
* the bufPage containing the result leaf index page
* by Author:
*/
DBBufPage* DBFileIndex::FindLeafPage(const char* key, int keyLength)
{
	DBBufPage* bufPage = manager->DBFileOpenPage(rootId);
	DBIndexPage* indexPage = (DBIndexPage*)&(bufPage->page);
	while(indexPage->pageType == INDEX_TYPE_NONLEAF)
	{
		int indexResult = -1;
		SearchPage(indexPage, key, keyLength, indexResult);
		int nextPid;
		if(indexResult == -1)
			nextPid = indexPage->firstPageId;
		else
		{
			nextPid = ((RowID*)(indexPage->data 
				+ indexPage->slot[indexResult]))->pageid;
		}
		assert(nextPid != -1);
		bufPage = manager->DBFileOpenPage(nextPid);
		indexPage = (DBIndexPage*)&(bufPage->page);
	}
	return bufPage;
}

DBFileIndex::DBFileIndex()
{
}

DBFileIndex::~DBFileIndex(void)
{
}

void DBFileIndex::initIndex(int inRootId, DBFileBufPageManager* inManager)
{
	manager = inManager;

	if(inRootId == -1)
	{
		DBBufPage* rootBufPage;
		manager->DBFileAllocPage(rootId, rootBufPage);
		DBIndexPage* indexPage = (DBIndexPage*)&(rootBufPage->page);

		indexPage->pageType = INDEX_TYPE_LEAF;
		InitPageSlot(indexPage);
		indexPage->firstPageId = -1;
		indexPage->addHead = 0;
		indexPage->parent = -1;
	}
	else
		rootId = inRootId;
}

void DBFileIndex::dropIndex()
{
	DBBufPage* rootBufPage = manager->DBFileOpenPage(rootId);
	DropPage(rootBufPage);
}

/**
* Funtion Description : Search a key in b+tree
* @para char* key
* key
* @para int keyLength
* key length
* @para RowID& rowid
* return value, rowid
* @return bool
* true: find
* false: not find
* by Author: Jimmy
*/
bool DBFileIndex::search(const char* key, int keyLength, RowID& rowid)
{
	assert(rootId != -1);
	DBBufPage* bufPage = FindLeafPage(key, keyLength);

	DBIndexPage* indexPage = (DBIndexPage*)&(bufPage->page);
	int indexResult = -1;
	if(SearchPage(indexPage, key, keyLength, indexResult))
	{	
		rowid = *(RowID*)(indexPage->data+indexPage->slot[indexResult]);
		return true;
	}
	else
	{
		return false;
	}
}

/**
* Funtion Description :Insert a (key, rowid) pair to b+tree
* @para char* key
* key
* @para int keyLength
* keylength
* @para RowID rowId
* rowid
* @return
* true: find and del
* false: del fail
* by Author: Jimmy
*/
bool DBFileIndex::insert(const char* key, int keyLength, RowID rowId)
{
	// find out the corresponding leaf page
	DBBufPage* bufPage = FindLeafPage(key, keyLength);

	// insert
	InsertToIndexPage(key, keyLength, bufPage, rowId);

	return true;
}

/**
* Funtion Description :Delete a (key, rowid) pair to b+tree
* @para char* key
* key
* @para int keyLength
* keyLength
* @return
* true: find and del
* false: del fail
* by Author: Jimmy
*/
bool DBFileIndex::del(const char* key, int keyLength)
{
	// find out the corresponding leaf page
	DBBufPage* bufPage = FindLeafPage(key, keyLength);

	// find the index of record
	int indexResult;
	if(SearchPage((DBIndexPage*)&(bufPage->page), key, keyLength, indexResult))
	{
		DeleteFromIndexPage(indexResult, bufPage);
		return true;
	}
	else
	{
		return false;
	}
}

/**
* Funtion Description : Update a pair, (oldkey, oldrowid) -> (newkey, newrowid)
* @para char* oldKey
* oldkey
* @para int oldKeyLength
* oldkey length
* @para char* newKey
* newkey
* @para int newKeyLength
* newkey length
* @para int newRowId
* new rowid
* @return
* true: find and del
* false: del fail
* by Author: Jimmy
*/
bool DBFileIndex::update(const char* oldKey, int oldKeyLength, const char* newKey
			, int newKeyLength, RowID newRowId)
{
	del(oldKey, oldKeyLength);
	insert(newKey, newKeyLength, newRowId);
	return true;
}

int DBFileIndex::getRootId() const
{
	return rootId;
}